package lyroot.entity;

import java.util.*;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : lyroot.entity
 * @Author :  cheungming
 * @CreateTime : 2024-07-23 08:52:57
 * @Description : RandomizedSet
 * @Version : 1.0
 */
public class RandomizedSet {

    // 存储数据
    List<Integer> nums;
    // 存储索引
    Map<Integer, Integer> map;

    Random random;

    public RandomizedSet() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        // 如果已经存在，返回false
        if (map.containsKey(val)) {
            return false;
        }
        // 否则，添加到nums和map中
        int index = nums.size();
        nums.add(val);
        map.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        // 如果不存在，返回false
        if (!map.containsKey(val)) {
            return false;
        }
        // 否则，删除nums和map中的数据
        // 删除map中的数据，直接删除key就行，删除nums中的数据，需要先获取索引，再删除
        // 获取索引
        int index = map.get(val);
        // 获取最后一个元素
        int last = nums.get(nums.size() - 1);
        // 替换
        nums.set(index, last);
        // 更新map
        map.put(last, index);
        // 删除最后一个元素
        nums.remove(nums.size() - 1);
        // 删除map中的数据
        map.remove(val);
        return true;

    }

    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}
